package week03;


/**
 * Description： 106. 从中序与后序遍历序列构造二叉树
 * https://leetcode-cn.com/problems/permutations-ii/
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 * Author: liujiao
 * Date: Created in 2022/1/18 17:56
 * email: liujiao@fcbox.com
 * Version: 0.0.1
 */
public class BuildTreeSolution {

    public static void main(String[] args) {
        int[] inorder = new int[]{9,3,15,20,7};
        int[] postorder = new int[]{9,15,7,20,3};
        TreeNode treeNode = buildTree(inorder, postorder);
        System.out.println(treeNode);

    }
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder, 0, inorder.length,
                postorder, 0, postorder.length);
    }


    private static TreeNode build(int[] inorder, int inLeft, int inRight,
                               int[] postorder, int postLeft, int postRight){

        if(inRight - inLeft < 1){ return null;}
        if (inRight - inLeft == 1) {
            return new TreeNode(inorder[inLeft]);
        }
        TreeNode root = new TreeNode(postorder[postRight - 1]);
        int rootIndex = 0;
        for(int i = inLeft; i < inRight; i++){
            if(inorder[i] == root.val){
                rootIndex = i;
            }
        }

        int LENGTH = rootIndex - inLeft;
        root.left = build(inorder, inLeft, rootIndex,
                postorder, postLeft, postLeft + LENGTH);
        root.right = build(inorder, rootIndex + 1, inRight,
                postorder,postLeft + LENGTH, postRight - 1);
        return root;
    }
}
